/**
 * @file 77.Combinations.cc
 * @author snow-tyan (zziywang@163.com)
 * @brief {Life is too short to learn cpp.}
 * @version 0.1
 * @date 2021-11-14
 * 
 * @copyright Copyright (c) 2021
 * 
 * 组合问题 N个数按一定规则找出k个数的集合
 * 77.组合 -- 剪枝
 * 216.组合总和III
 * 17.电话号码的字母组合 -- 多个集合求组合
 * 39.组合总和 -- 数组本身无重复
 * 40.组合总和II -- 难点在于数组本身有重复，要求解集无重复
 */

#include <algorithm>
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
// #define TEST17

template <typename T>
void print(const T &Containers)
{
    typename T::const_iterator it = Containers.begin();
    while (it != Containers.end()) {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
}

class Solution
{
private:
    vector<vector<int>> _res;
    vector<int> _path;

public:
    // 77. 返回[1,n]区间内所有k个数的组合
    vector<vector<int>> combine(int n, int k)
    {
        backtracking77(n, k, 1);
        return _res;
    }

private:
    void backtracking77(int n, int k, int startidx)
    {
        if (_path.size() == k) {
            _res.emplace_back(_path);
            return;
        }
        for (int i = startidx; i < n + 1; ++i) {
            // 剪枝优化：当剩下的数字都不足k - len(_path)，就不用再遍历了
            if (n - i + 1 < k - _path.size()) {
                continue;
            }
            _path.push_back(i);
            backtracking77(n, k, i + 1);
            _path.pop_back();
        }
    }

public:
    // 216. [1,9]中所有和为n的k个数组合
    vector<vector<int>> combinationSum3(int k, int n)
    {
        backtracking216(k, n, 1, 0);
        return _res;
    }

private:
    void backtracking216(int k, int n, int startidx, int sum)
    {
        if (sum >= n || _path.size() == k) {
            if (sum == n && _path.size() == k) {
                _res.emplace_back(_path);
            }
            return;
        }
        for (int i = startidx; i <= 9; ++i) {
            // 剪枝，如果剩下数加上_path中的数都不足k个
            if (9 - i + 1 < k - _path.size()) {
                continue;
            }
            sum += i;
            _path.push_back(i);
            backtracking216(k, n, i + 1, sum);
            sum -= i;
            _path.pop_back();
        }
    }
#ifdef TEST17
public:
    // 17. 对每个数字枚举 多个数字进行组合
    unordered_map<char, string> mp = {
        {'2', "abc"},
        {'3', "def"},
        {'4', "ghi"},
        {'5', "jkl"},
        {'6', "mno"},
        {'7', "pqrs"},
        {'8', "tuv"},
        {'9', "wxyz"}};
    vector<string> res;
    string path;
    vector<string> letterCombinations(string digits)
    {
        // 仅包含2-9的字符串
        // map={2:"abc", 3:"def", 4:"ghi", 5:"jkl", 6:"mno", 7:"pqrs", 8:"tuv",9:"wxyz"};
        backtracking17(digits, 0);
        return res;
    }

private:
    void backtracking17(string &digits, int index)
    {
        if (index == digits.size()) {
            res.emplace_back(path);
            return;
        }
        char key = digits[index];
        string letters = mp[key];
        // digits[idx]才是回溯时的变量
        for (int i = 0; i < letters.size(); ++i) {
            path.push_back(letters[i]);
            backtracking17(digits, index + 1);
            path.pop_back();
        }
    }
#endif
public:
    // 39. 从数组中选出和为target的元素组合，数组中元素可使用多次
    // 数组本身不重复
    vector<vector<int>> combinationSum(vector<int> &candidates, int target)
    {
        backtracking39(candidates, target, 0, 0);
        return _res;
    }

private:
    void backtracking39(vector<int> &candidates, int target, int startidx, int sum)
    {
        if (sum >= target) {
            if (sum == target) {
                _res.emplace_back(_path);
            }
            return;
        }
        for (int i = startidx; i < candidates.size(); ++i) {
            sum += candidates[i];
            _path.push_back(candidates[i]);
            backtracking39(candidates, target, i, sum);
            sum -= candidates[i];
            _path.pop_back();
        }
    }

public:
    // 40. 从数组中选出和为target的元素组合，数组中元素只可使用1次
    // 数组本身有重复，解集要求不重复
    vector<vector<int>> combinationSum2(vector<int> &candidates, int target)
    {
        // sort让相同元素紧挨着
        std::sort(candidates.begin(), candidates.end());
        backtracking40(candidates, target, 0, 0);
        return _res;
    }

private:
    void backtracking40(vector<int> &candidates, int target, int startidx, int sum)
    {
        if (sum >= target) {
            if (sum == target) {
                _res.emplace_back(_path);
            }
            return;
        }
        for (int i = startidx; i < candidates.size(); ++i) {
            // 跳过重复元素
            if (i > startidx && candidates[i] == candidates[i - 1]){
                continue;
            }
            sum += candidates[i];
            _path.push_back(candidates[i]);
            backtracking40(candidates, target, i + 1, sum);
            sum -= candidates[i];
            _path.pop_back();
        }
    }
};

Solution solve = Solution();

void test77()
{
    vector<vector<int>> nums = solve.combine(4, 2);
    for (auto &num : nums) {
        print(num);
    }
}
void test216()
{
    vector<vector<int>> nums = solve.combinationSum3(9, 45);
    for (auto &num : nums) {
        print(num);
    }
}
#ifdef TEST17
void test17()
{
    print(solve.letterCombinations("2"));
}
#endif

void test39()
{
    vector<int> candidates = {2, 3, 5};
    int target = 8;
    vector<vector<int>> nums = solve.combinationSum(candidates, target);
    for (auto &num : nums) {
        print(num);
    }
}

void test40()
{
    vector<int> candidates = {10, 1, 2, 7, 6, 1, 5};
    int target = 8;
    vector<vector<int>> nums = solve.combinationSum2(candidates, target);
    for (auto &num : nums) {
        print(num);
    }
}

int main()
{
    // test77();
    // test216();
    // test17();
    // test39();
    test40();
    return 0;
}